package club.xiaojiawei.binarytree;

import java.util.*;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/9/22 10:10 PM
 * @question 107. 二叉树的层序遍历 II
 * @description 给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
 */
public class LevelOrderBottom107 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        TreeNode left = new TreeNode(9);
        TreeNode right = new TreeNode(20);
        right.left = new TreeNode(15);
        right.right = new TreeNode(7);
        root.left = left;
        root.right = right;
        List<List<Integer>> result = levelOrderBottom(root);
        System.out.println(result);
    }

    /**
     * 递归（手动求出数的高度）
     * @param root
     * @return
     */
    public static List<List<Integer>> levelOrderBottom(TreeNode root) {
        if (root == null){
            return new ArrayList<>();
        }
        int height = height(root);
        ArrayList[] result = new ArrayList[height];
        recursion(height - 1, result, root);
        return Arrays.asList(result);
    }

    /**
     * 官方-迭代+BFS
     * @param root
     * @return
     */
    public static List<List<Integer>> levelOrderBottom2(TreeNode root) {
        List<List<Integer>> levelOrder = new LinkedList<List<Integer>>();
        if (root == null) {
            return levelOrder;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                TreeNode left = node.left, right = node.right;
                if (left != null) {
                    queue.offer(left);
                }
                if (right != null) {
                    queue.offer(right);
                }
            }
            levelOrder.add(0, level);
        }
        return levelOrder;
    }

    /**
     * 民间-递归
     * @param root
     * @return
     */
    public static List<List<Integer>> levelOrderBottom3(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        dfs(root, 0, res);
        return res;
    }

    public static void dfs(TreeNode node, int depth, List<List<Integer>> res) {
        if(node==null){
            return;
        }
        if(depth==res.size()){
            res.add(0,new ArrayList<>());
        }
        res.get(res.size()-depth-1).add(node.val);
        dfs(node.left,depth+1,res);
        dfs(node.right,depth+1,res);
    }

    /**
     * 求树的高度
     * @param root
     * @return
     */
    public static int height(TreeNode root){
        return Math.max(root.left == null? 0 : height(root.left), root.right == null? 0 : height(root.right)) + 1;
    }

    public static void recursion(int n, ArrayList[] list, TreeNode node){
        if (node == null){
            return;
        }
        ArrayList<Integer> current;
        if ((current = list[n]) == null){
            current = new ArrayList<>();
            list[n] = current;
        }
        current.add(node.val);
        recursion(n - 1, list, node.left);
        recursion(n - 1, list, node.right);
    }

    static class TreeNode{

        private int val;

        private TreeNode left;

        private TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }
    }
}
